package 题目集.前缀和;


import org.junit.Test;
import 题目集.单调栈or队列.单调队列.舍弃可能性.搭配前缀和;

/**
 * 好题
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组是数组中的一个连续部分。
 * https://leetcode.cn/problems/maximum-subarray/description/
 */
public class 最大子数组和 {
    /**
     * 暴力思路：
     *      枚举每个起点对应的每个终点，求这些区间的最大值。
     *      时间复杂度O(n^2)
     * 其实这题如何使用前缀和，与{@link 搭配前缀和}那题挺像的，但当时那题没思考出来。
     *      我们可以将题目分析为：已知数组前缀和，求 s[r]-s[l-1]的最大值。
     *      最大值一定满足这样的要求：
     *          s[l-1]<s[l-2]且（r!=l）s[l-1]<s[l]。如果不符合这个要求，则s[r]-s[l-2]或s[r]-s[l]是最优解。
     *          所以我们可以在枚举右端点的时候，计算与之前最小s[l]的差，同时更新最小s[l]。
     */
    public int maxSubArray(int[] nums) {
        int[] sum=new int[nums.length+1];
        for (int i = 1; i < sum.length; i++) {
            sum[i]=sum[i-1]+nums[i-1];
        }
        int min=0;
        int res=nums[0];
        for (int i = 1; i < sum.length; i++) {
            int cur = sum[i] - sum[min];
            if (cur >res){
                res=cur;
            }
            if (sum[i]<sum[min]){
                min=i;
            }
        }
        return res;
    }
    @Test
    public void test(){
        System.out.println(maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
}
